package com.chj.dfs.class04;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Code05_CombinationSum {
	private static void combinationSum(List<Integer> cur, int sums[], int target) {
		// 终止条件必须要有
		if (target == 0) {
			System.out.println(Arrays.toString(cur.toArray()));
			return;
		}
		for (int i = 0; i < sums.length; i++) {
			// 逻辑处理
			// 如果当前值大于target我们就不要选了
			if (target < sums[i])
				continue;
			// 由于List是引用传递，所以这里要重新创建一个
			List<Integer> list = new ArrayList<>(cur);
			// 把数据加入到集合中
			list.add(sums[i]);
			// 递归调用
			combinationSum(list, sums, target - sums[i]);
		}
	}

	private static void combinationSum02(List<Integer> cur, int sums[], int target, int numSub) {
		// 终止条件必须要有
		if (target == 0) {
			System.out.println(Arrays.toString(cur.toArray()));
			return;
		}

//		if (target < 2 || target < 3 || target < 5) {
//			return;
//		}

		if ((numSub == 2 && target < 2) || (numSub == 3 && target < 3) || (numSub == 5 && target < 5)) {
			return;
		}
//		for (int i = 0; i < sums.length; i++) {
//			// 逻辑处理
//			// 如果当前值大于target我们就不要选了
//			if (target < sums[i])
//				continue;
		// 由于List是引用传递，所以这里要重新创建一个
		List<Integer> list = new ArrayList<>(cur);
		// 把数据加入到集合中
		list.add(2);
		// 递归调用
		combinationSum02(list, sums, target - 2, 2);

		List<Integer> list2 = new ArrayList<>(cur);
		// 把数据加入到集合中
		list2.add(3);
		combinationSum02(list2, sums, target - 3, 3);

		List<Integer> list3 = new ArrayList<>(cur);
		// 把数据加入到集合中
		list3.add(5);
		combinationSum02(list3, sums, target - 5, 5);
//		}
	}

	public static void main(String[] args) {
		{
			List<Integer> cur = new ArrayList<>();
			int sums[] = { 2, 3, 5 };
			int target = 8;
			combinationSum(cur, sums, target);
		}
		System.out.println("===========");
		{
			List<Integer> cur = new ArrayList<>();
			int sums[] = { 2, 3, 5 };
			int target = 8;
			combinationSum02(cur, sums, target, 0);
		}
	}
}
